#pragma once
#include <ostream>
template <typename T>
class Queue {
public:
	Queue(int maxSize);
	~Queue();
	bool isEmpty();
	bool isFull();
	bool left(T& x);
	bool right(T& x);
	bool addLeft(T x);
	bool addRight(T x);
	bool deleteLeft(T& x);
	bool deleteRight(T& x);
	void output(std::ostream& out);
private:
	int front, rear;
	T* element;
	int maxSize;
};
template <typename T>
Queue<T>:: Queue(int maxSize){
	this->maxSize = maxSize;
	element = new T[maxSize];
	front = rear = 0;
}
template <typename T>
Queue<T>::~Queue() {
	delete[] element;
}
template <typename T>
bool Queue<T>::isEmpty() {
	if (rear == front)
		return true;
	return false;
}
template <typename T>
bool Queue<T>::isFull() {
	if ((rear+1)%maxSize == front)
		return true;
	return false;
}
template <typename T>
bool Queue<T>::left(T& x) {
	if (this->isEmpty())
		return false;
	x = element[front];
	return true;
}
template <typename T>
bool Queue<T>::right(T& x) {
	if (this->isEmpty())
		return false;
	if (rear == 0) {
		x = element[maxSize-1];
		return true;
	}
	x = element[rear - 1];
	return true;
}
template <typename T>
bool Queue<T>::addLeft(T x) {
	if (this->isFull())
		return false;
	if (this->isEmpty()) {
		front = 0;
		rear = 1;
		element[front] = x;
		return true;
	}
	if (front == 0) 
		front = maxSize-1;
	else
		front = front - 1;
	element[front] = x;
	return true;
}
template <typename T>
bool Queue<T>::addRight(T x){
	if (this->isFull())
		return false;
	if (this->isEmpty()) {
		front = 0;
		rear = 1;
		element[0] = x;
		return true;
	}
	element[rear] = x;
	rear = (rear + 1) % maxSize;
	return true;
}
template <typename T>
bool Queue<T>::deleteLeft(T& x) {
	if (this->isEmpty())
		return false;
	front = (front + 1) % maxSize;
	return true;
}
template <typename T>
bool Queue<T>::deleteRight(T& x) {
	if (this->isEmpty())
		return false;
	if (rear == 0)
		rear = maxSize-1;
	else
		rear = rear - 1;
	return true;
}
template <typename T>
void Queue<T>::output(std::ostream& out) {
	if (this->isEmpty()) {
		out << '\n';
		return;
	}
	int i = front;
	for ( i = front; (i+1)%maxSize != rear; i = (i + 1)%maxSize) {

		out << element[i]<<" ";
	}
	out << element[i]<<'\n';
}